package leetcode_zh

import (
	"go-study/src/leetcode"
	"go-study/src/utils"
	"math"
	"strconv"
	"time"
)

/**
 * @Description: 1. 两数之和
 * @Keyword: 简单
 * @Author: kami
 * @Date: 2022/4/3 17:38
 **/
func twoSum(nums []int, target int) []int {
	var targetMap = make(map[int]int)
	for i := 0; i < len(nums); i++ {
		var need = target - nums[i]
		if valIdx, ok := targetMap[need]; ok {
			return []int{valIdx, i}
		}
		targetMap[nums[i]] = i
	}
	return nil
}

/**
 * @Description: 2. 两数相加
 * @Keyword: 链表
 * @Author: kami
 * @Date: 2022/4/3 17:57
 **/
func addTwoNumbers(l1 *leetcode.ListNode, l2 *leetcode.ListNode) *leetcode.ListNode {
	virtual := &leetcode.ListNode{}
	res := virtual
	var take int
	for l1 != nil || l2 != nil {
		var val int
		if l1 != nil {
			val += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			val += l2.Val
			l2 = l2.Next
		}
		if take > 0 {
			val += 1
		}
		if val > 9 {
			val %= 10
			take = 1
		} else {
			take = 0
		}
		curNode := &leetcode.ListNode{
			Val: val,
		}
		virtual.Next = curNode
		virtual = curNode
	}
	if take > 0 {
		curNode := &leetcode.ListNode{
			Val: 1,
		}
		virtual.Next = curNode
		virtual = curNode
	}
	return res.Next
}

/**
 * @Description: 3. 无重复字符的最长子串
 * @Keyword: 滑动窗口
 * @Author: kami
 * @Date: 2022/4/3 18:33
 **/
func lengthOfLongestSubstring(s string) int {
	if len(s) == 0 {
		return 0
	}
	var max = 1
	var curMax = 1
	var windowMap = map[byte]int{
		s[0]: 0,
	}
	var start int
	for i := 1; i < len(s); i++ {
		if idx, ok := windowMap[s[i]]; ok && idx >= start {
			curMax = i - idx
			start = idx + 1
		} else {
			curMax += 1
		}
		if curMax > max {
			max = curMax
		}
		windowMap[s[i]] = i
	}
	return max
}

/**
 * @Description: 4. 寻找两个正序数组的中位数
 * @Keyword: 第K小数字
 * @Author: kami
 * @Date: 2022/4/4 13:26
 **/
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	var m = len(nums1)
	var n = len(nums2)
	var left = (m + n + 1) / 2
	var right = (m + n + 2) / 2
	return float64(findKth(nums1, 0, nums2, 0, left)+findKth(nums1, 0, nums2, 0, right)) / 2.0
}

func findKth(nums1 []int, i int, nums2 []int, j int, k int) int {

	if i >= len(nums1) {
		return nums2[j+k-1]
	}
	if j >= len(nums2) {
		return nums1[i+k-1]
	}

	if k == 1 {
		return utils.GetMin(nums1[i], nums2[j])
	}
	var midVal1 = math.MaxInt
	if i+k/2-1 < len(nums1) {
		midVal1 = nums1[i+k/2-1]
	}
	var midVal2 = math.MaxInt
	if j+k/2-1 < len(nums2) {
		midVal2 = nums2[j+k/2-1]
	}

	if midVal1 < midVal2 {
		return findKth(nums1, i+k/2, nums2, j, k-k/2)
	} else {
		return findKth(nums1, i, nums2, j+k/2, k-k/2)
	}
}

/**
 * @Description: 5. 最长回文子串
 * @Keyword: 构造中心对称 #a#b#c#d#d#c#b#a# 添加N+1个#
 * @Author: kami
 * @Date: 2022/4/10 15:11
 **/
func longestPalindrome(s string) string {
	var syml byte = '#'
	var addedS = []byte{syml}
	for i := 0; i < len(s); i++ {
		addedS = append(addedS, s[i], syml)
	}

	var res []byte
	for i := 0; i < len(addedS); i++ {
		var curRes = getMaxPalindromeStr(addedS, i)
		if len(curRes) > len(res) {
			res = curRes
		}
	}

	var trimRes []byte
	for i := 0; i < len(res); i++ {
		if res[i] != syml {
			trimRes = append(trimRes, res[i])
		}
	}
	return string(trimRes)
}

func getMaxPalindromeStr(s []byte, start int) []byte {
	if start < 0 || start >= len(s) {
		return []byte{}
	}
	var halfLen = 0
	for i := 1; i <= start; i++ {
		var (
			left  = start - i
			right = start + i
		)

		if left < 0 || right >= len(s) || s[left] != s[right] {
			break
		}
		halfLen += 1

	}
	if halfLen > 0 {
		return s[start-halfLen : start+halfLen+1]
	}

	return s[start : start+1]
}

/**
 * @Description: 7. 整数反转
 * @Keyword: 不能用64为整形
 * @Author: kami
 * @Date: 2022/4/10 16:25
 **/
func reverse(x int) int {
	var rev int
	for x != 0 {
		if rev < math.MinInt32/10 || rev > math.MaxInt32/10 {
			return 0
		}
		digit := x % 10
		x /= 10
		rev = rev*10 + digit
	}
	return rev
}

/**
 * @Description: 479. 最大回文数乘积
 * @Keyword: 枚举
 * @Author: kami
 * @Date: 2022/4/16 12:16
 **/
func largestPalindrome(n int) int {
	if n == 1 {
		return 9
	}
	upper := int(math.Pow10(n)) - 1
	for left := upper; ; left-- { // 枚举回文数的左半部分
		p := left
		for x := left; x > 0; x /= 10 {
			p = p*10 + x%10 // 翻转左半部分到其自身末尾，构造回文数 p
		}
		for x := upper; x*x >= p; x-- {
			if p%x == 0 { // x 是 p 的因子
				return p % 1337
			}
		}
	}
}

/**
 * @Description: 9. 回文数
 * @Keyword:
 * @Author: kami
 * @Date: 2022/4/17 19:08
 **/
func isPalindrome(x int) bool {
	if x == 0 {
		return true
	}
	if x%10 == 0 {
		return false
	}
	xStr := strconv.Itoa(x)
	for i := 0; i < len(xStr)/2; i++ {
		if xStr[i] != xStr[len(xStr)-i-1] {
			return false
		}
	}
	return true
}

/**
 * @Description: 139. 单词拆分
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/5/1 15:11
 **/
func wordBreak(s string, wordDict []string) bool {
	dictMap := make(map[string]bool)
	for i := 0; i < len(wordDict); i++ {
		dictMap[wordDict[i]] = true
	}
	var dp = make([]bool, len(s))
	for i := 0; i < len(s); i++ {
		for j := 0; j <= i; j++ {
			var right = s[j : i+1]
			if dictMap[right] && (j == 0 || dp[j-1]) {
				dp[i] = true
				break
			}
		}
	}
	return dp[len(s)-1]
}

/**
 * @Description: 1360. 日期之间隔几天
 * @Keyword: 日期类
 * @Author: kami
 * @Date: 2022/5/2 14:54
 **/
func daysBetweenDates(date1 string, date2 string) int {
	var format = "2006-01-02"
	day1, _ := time.Parse(format, date1)
	day2, _ := time.Parse(format, date2)
	res := int(day2.Sub(day1).Hours() / 24)
	if res > 0 {
		return res
	}
	return -res
}

/**
 * @Description: 剑指 Offer 33. 二叉搜索树的后序遍历序列 中等
 * @Keyword: 递归，最右跟节点，第一个比根节点大的是其右子树，都比根节点大，如果出现比根节点小的则不为二叉搜索树
			后续 左右中
 * @Author: kami
 * @Date: 2022/6/23 15:10
 **/
func verifyPostorder(postorder []int) bool {
	return verifyHelper(postorder, 0, len(postorder)-1)
}

/*
左闭右闭
*/
func verifyHelper(postOrder []int, left, right int) bool {
	if left >= right {
		return true
	}
	// 寻找右子树
	var mid = left
	for postOrder[mid] < postOrder[right] {
		mid++
	}
	// 右子树都要大于跟节点
	var tempMid = mid
	for tempMid < right {
		if postOrder[tempMid] < postOrder[right] {
			return false
		}
		tempMid++
	}
	// 递归判断左右子树
	return verifyHelper(postOrder, left, mid-1) && verifyHelper(postOrder, mid, right-1)

}
